<HTML>
<BODY BGCOLOR="white">

<center>
<FONT SIZE=+2 COLOR="#BB0000">CS346 - Spring 2014<BR>Database System Implementation</FONT>
</center>

<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>RedBase Part 2: The Indexing Component</b></center>
<center><b>Due Sunday April 27</b></center>
</font></td></tr>
</table>

<ul>
<li> <a href="#intro">Introduction</a>
<li> <a href="#interface"><b>IX Interface</b></a>
<li> <a href="#impl">Implementation Details</a>
<li> <a href="#misc">Miscellaneous</a>
</ul>

<a name="intro">
<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>Introduction</b></center>
</font></td></tr>
</table>

The second part of the RedBase system you will implement is the
<i>Indexing</i> (<i>IX</i>) component.  The IX component provides
classes and methods for managing persistent indexes over unordered
data records stored in paged files.  Each data file may have any
number of (single-attribute) indexes associated with it.  The indexes
ultimately will be used to speed up processing of relational
selections, joins, and condition-based update and delete operations.
Like the data records themselves, the indexes are stored in paged
files.  Hence, in implementing the IX component you will use the PF
component similarly to the way you used it for Part 1.  In the overall
RedBase architecture, you can think of the IX and RM components as
sitting side by side above the PF component.

<p>
The indexing technique you will implement in the IX component is <i>B+
trees</i>.  B+ trees will be reviewed in class, they were covered in
CS245, and they are discussed in detail in most comprehensive database
textbooks.  Because a "perfect" implementation of B+ trees turn out to
be quite complex, we are allowing some simplifications as discussed in
the <a href="#impl">Implementation Details</a> section below.

<p>
All class names, return codes, constants, etc. in this component
should begin with the prefix IX.  Each B+ tree index can be stored in
one paged file from the PF component.  Some specific implementation
suggestions are given <a href="#impl">later in this document</a>, but
you should be aware that we're giving away fewer details for this
component than we did for the RM component.

<p>
<i>Note: You can certainly find pseudocode and perhaps even software
packages for B+ trees available publicly. In fact, a previous CS346
TA, based on his work for the class, wrote a paper specifying <a
target="_blank" href="jannink.pdf">B+ tree deletion algorithms</a>
(pdf). You are welcome to use anything you find, as long as you
provide proper acknowledgment when you turn in this part of the
project.  However, we do warn against simply copying available code
and then trying to modify it to fit the RedBase specification.  That
approach is very likely to be more difficult than using available code
or pseudocode for algorithmic ideas and reference.</i>

<a name="interface">
<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>IX Interface</b></center>
</font></td></tr>
</table>

The IX interface you will implement consists of three classes: the
<tt>IX_Manager</tt> class, the <tt>IX_IndexHandle</tt> class, and the
<tt>IX_IndexScan</tt> class.  In addition, there is an
<tt>IX_PrintError</tt> routine for printing messages associated with
nonzero IX return codes.  To obtain an initial header file with the
public method declarations for this interface (along with links for
some other files mentioned below) run the <tt>setup</tt> script
described in the <a href="logistics.html">RedBase
Logistics</a> document with argument "<tt>2</tt>" (for project part
2).  As usual, all IX component public methods (except constructors
and destructors) should return 0 if they complete normally and a
nonzero return code otherwise.

<h3> IX_Manager Class </h3>

The <tt>IX_Manager</tt> class handles the creation, deletion, opening,
and closing of indexes.  Your program should create exactly one
instance of this class.  All necessary initialization of the IX
component should take place within the constructor for the
<tt>IX_Manager</tt> class.  Note that this constructor takes as a
parameter the instance of the <tt>PF_Manager</tt> class, which you
should already have created (refer to the <a
href="pf.html">PF</a> and <a
href="rm.html">RM</a>
documents).  Any necessary clean-up in the IX component should take
place within the destructor for the <tt>IX_Manager</tt> class.

<pre>
class IX_Manager {
  public:
       IX_Manager   (PF_Manager &pfm);              // Constructor
       ~IX_Manager  ();                             // Destructor
    RC CreateIndex  (const char *fileName,          // Create new index
                     int        indexNo,
                     AttrType   attrType,
                     int        attrLength);
    RC DestroyIndex (const char *fileName,          // Destroy index
                     int        indexNo);
    RC OpenIndex    (const char *fileName,          // Open index
                     int        indexNo,
                     IX_IndexHandle &indexHandle);
    RC CloseIndex   (IX_IndexHandle &indexHandle);  // Close index
};
</pre>

<h4>
RC CreateIndex (const char *fileName, int indexNo, 
                AttrType attrType, int attrLength)
</h4>

This method creates an index numbered <tt>indexNo</tt> on the data
file named <tt>fileName</tt>.  You may assume that clients of this
method will ensure that the <tt>indexNo</tt> parameter is unique and
nonnegative for each index created on a file.  Thus, <tt>indexNo</tt>
can be used along with <tt>fileName</tt> to generate a unique file
name (e.g., "<tt>fileName.indexNo</tt>") that you can use for the PF
component file storing the new index.  The type and length of the
attribute being indexed are described by parameters <tt>attrType</tt>
and <tt>attrLength</tt>, respectively.  As in the RM component,
<tt>attrLength</tt> should be 4 for attribute types <tt>INT</tt> or
<tt>FLOAT</tt>, and it should be between 1 and <tt>MAXSTRINGLEN</tt>
for attribute type <tt>STRING</tt>.  This method should establish an
empty index by creating the PF component file and initializing it
appropriately.

<h4>
RC DestroyIndex (const char *fileName, int indexNo)
</h4>

This method should destroy the index numbered <tt>indexNo</tt> on the
data file named <tt>fileName</tt> by destroying the PF component file
used to store the index.

<h4>
RC OpenIndex (const char *fileName, int indexNo, IX_IndexHandle &indexHandle)
</h4>

This method should open the index numbered <tt>indexNo</tt> on the
data file named <tt>fileName</tt> by opening the PF component file
used to store the index.  If the method is successful, the
<tt>indexHandle</tt> object should become a handle for the open index.
The index handle is used to insert into and delete entries from the
index (see the <tt>IX_IndexHandle</tt> methods below), and it can be
passed into an <tt>IX_IndexScan</tt> constructor (see below) for
performing a scan using the index.  As with RM component files,
clients should be able to open an index more than once for reading
using a different <tt>indexHandle</tt> object each time.  However, you
may make the assumption (without checking it) that if a client is
modifying an index, then no other clients are using an
<tt>indexHandle</tt> to read or modify that index.

<h4>
RC CloseIndex (IX_IndexHandle &indexHandle)
</h4>

This method should close the open index referred to by
<tt>indexHandle</tt> by closing the PF component file used to store
the index.

<h3> IX_IndexHandle Class </h3>

The <tt>IX_IndexHandle</tt> class is used to insert and delete index
entries, and to force pages of an index's files to disk. To perform
these operations, a client first creates an instance of this class and
passes it to the <tt>IX_Manager::OpenIndex</tt> method described
above.

<pre>
class IX_IndexHandle {
  public:
       IX_IndexHandle  ();                             // Constructor
       ~IX_IndexHandle ();                             // Destructor
    RC InsertEntry     (void *pData, const RID &rid);  // Insert new index entry
    RC DeleteEntry     (void *pData, const RID &rid);  // Delete index entry
    RC ForcePages      ();                             // Copy index to disk
 };
</pre>

<h4>
RC InsertEntry (void *pData, const RID &rid)
</h4>

For this and the following two methods, it is incorrect if the
<tt>IX_IndexHandle</tt> object for which the method is called does not
refer to an open index.  This method should insert a new entry into
the index associated with <tt>IX_IndexHandle</tt>.  Parameter
<tt>pData</tt> points to the attribute value to be inserted into the
index, and parameter <tt>rid</tt> identifies the record with that
value to be added to the index.  Hence, this method effectively
inserts an entry for the pair <tt>(*pData,rid)</tt> into the index.
(The index should contain only the record's RID, not the record
itself.)  If the indexed attribute is a character string of length
<i>n</i>, then you may assume that <tt>*pData</tt> is exactly <i>n</i>
bytes long; similarly for parameter <tt>*pData</tt> in the next
method.  This method should return a nonzero code if there is already
an entry for <tt>(*pData,rid)</tt> in the index.

<h4>
RC DeleteEntry (void *pData, const RID &rid)
</h4>

This method should delete the entry for the <tt>(*pData,rid)</tt> pair
from the index associated with <tt>IX_IndexHandle</tt>.  Although
clients of the IX Component typically will ensure that
<tt>DeleteEntry</tt> is not called for entries that are not in the
index, for debugging purposes you may want to return a (positive)
error code if such a call is made.

<h4>
RC ForcePages ()
</h4>

This method should copy to disk all pages associated with the
<tt>IX_IndexHandle</tt>.  The index page contents are forced to disk
by calling <tt>PF_FileHandle::ForcePages</tt> for the index file.

<h3> IX_IndexScan Class </h3>

The <tt>IX_IndexScan</tt> class is used to perform condition-based scans
over the entries of an index.

<pre>
class IX_IndexScan {
  public:
       IX_IndexScan  ();                                 // Constructor
       ~IX_IndexScan ();                                 // Destructor
    RC OpenScan      (const IX_IndexHandle &indexHandle, // Initialize index scan
                      CompOp      compOp,
                      void        *value,
                      ClientHint  pinHint = NO_HINT);           
    RC GetNextEntry  (RID &rid);                         // Get next matching entry
    RC CloseScan     ();                                 // Terminate index scan
 };
</pre>

<h4>
RC OpenScan (const IX_IndexHandle &indexHandle, CompOp compOp, void *value, ClientHint pinHint = NO_HINT)
</h4>

This method should initialize a condition-based scan over the entries
in the open index referred to by parameter <tt>indexHandle</tt>.  Once
underway, the scan should produce the RIDs of all records whose
indexed attribute value compares in the specified way with the
specified value.  Parameters <tt>compOp</tt> and <tt>value</tt> are
exactly as in the <tt>RM_FileScan::OpenScan</tt> method (including the
possibility that <tt>compOp=NO_OP</tt> and <tt>value</tt> is a null
pointer, indicating a complete scan); please refer to the <a
href="rm.html">RM
Component</a> document for details.  The only exception is that for B+
tree scans, you may choose to disallow comparison operator
<tt>NE_OP</tt> (not-equal).  You will need to cast parameter
<tt>value</tt> into the appropriate type for the attribute (or, in the
case of an integer or float, copy it into a separate variable to avoid
alignment problems), as in the RM component.  Also as in method
<tt>IX_IndexHandle::InsertEntry</tt>, if the indexed attribute is a
character string of length <i>n</i>, then you may assume that <tt>
value</tt> is exactly <i>n</i> bytes long.  As in RM component file
scans, optional parameter <tt>pinHint</tt> is included so that
higher-level RedBase components using an IX component index scan can
suggest a specific page-pinning strategy for the IX component to use
during the index scan, to achieve maximum efficiency.  Exploiting this
parameter, either now or later, is entirely optional.

<h4>
RC GetNextEntry (RID &rid)
</h4>

This method should set output parameter <tt>rid</tt> to be the RID of
the next record in the index scan.  This method should return
<tt>IX_EOF</tt> (a positive return code that you define) if there are
no index entries left satisfying the scan condition.  You may assume
that IX component clients will not close the corresponding open index
while a scan is underway.

<h4>
RC CloseScan ()
</h4>

This method should terminate the index scan.

<h3> IX_PrintError </h3>

<h4>
void IX_PrintError (RC rc);
</h4>

This routine should write a message associated with the nonzero IX
return code <tt>rc</tt> onto the Unix <tt>stderr</tt> output stream.
This routine has no return value.

<a name="impl">
<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>Implementation Details</b></center>
</font></td></tr>
</table>

<ul>

<li> As with Part 1, you are free to use alternative design ideas to
those suggested here if you believe your ideas will improve the
structure or performance of your code.  The only thing that you must
not alter is the interface itself, although you are free to extend it
either now or as the project progresses.

<p><li> Each node of a B+ tree can be stored in one page of the
corresponding PF file.  Logically, index entries have the form
<tt>(attrValue,rid)</tt>, indicating that in the data file being
indexed there is a record with RID <tt>rid</tt> whose value for the
indexed attribute is <tt>attrValue</tt>.  In one straightforward
design the leaves of the tree are structurally identical to internal
nodes, i.e., they contain attribute values and page pointers
(numbers), and there is a separate "bucket" page (pointed to from the
leaf nodes) for each attribute value, containing the list of RIDs for
that value.  Note that although this straightforward design is
certainly acceptable for your project, it is very inefficient when the
number of RIDs for each attribute value is low -- buckets will be
nearly empty.  There are numerous improvements or alternatives to this
straightforward design.

<ul>

<li><b>Simplification</b>: You do not need to handle the case
where the number of RIDs for a single attribute value is so large that
all RIDs for that value cannot be stored on one page, but you should
detect if such an overflow occurs and generate a nonzero return
code.

<li><b>Small amount of extra credit</b>: Accommodate any number of
RIDs for an attribute value, typically through bucket chaining.

</ul>

<p><li> The three fundamental B+ tree operations -- <i>search</i>
(which extends to scan), <i>insertion</i>, and <i>deletion</i> -- vary
quite a bit in their implementation complexity.  We suggest that you
get search and insertion running first, and then worry about deletion.
In fact, implementing a completely correct delete operation in B+
trees turns out to be quite difficult.

<ul>

<li><b>Simplification</b>: You may implement <i>lazy deletion</i>.  In
this approach, when an entry is deleted, even if it causes a leaf page
to become less than half full no redistribution or node merging takes
place -- the underfull page remains in the tree.  When a leaf page
becomes empty the node is removed from the tree and an entry is
removed from its parent, but again no redistribution or node merging
takes place.

<li><b>Small amount of credit deducted:</b> Even simpler than lazy
deletion is <i>tombstones</i>.  In this approach, when an entry is
deleted it is replaced by a special marker indicating an empty slot
(which may be reused later).  Tree nodes are never deleted or merged,
although empty buckets should be deleted.  You cannot receive full
credit on the IX component if you implement tombstones, but it is an
option to consider if you're pressed for time.

<li><b>Medium amount of extra credit:</b> Implementing fully correct
(i.e., rebalancing) deletion is quite complex, with a number of tricky
end cases.  We will be duly impressed if you do so.

</ul>
Regardless of which approach you use, deletion must work: once an IX
component client asks for an entry to be deleted, that entry should
never appear in a subsequent index scan.

<p><li> We strongly suggest that you implement your B+ tree operations
using recursive algorithms.  Although you may find it somewhat
difficult to understand these algorithms at first, using a recursive
approach will greatly simplify your coding task.

<p><li> Index scans will be used by higher-level components when
executing selection, join, and delete operations, as well as update
operations on attributes other than the indexed attribute.  Thus, each
index entry scanned will either be used to fetch (and possibly update)
a record, or to delete a record.  (The <tt>insert</tt> operation
inserts one record at a time.)  While making an index scan work
correctly for selection, join, and non-index-key update operations is
relatively straightforward, deletion operations are more complicated,
even when using the simplified approaches to deletion described above.
You must ensure that it is possible to use an index scan to find and
then delete all index entries satisfying a condition.  That is, the
following client code segment should work:

<pre>
   IX_IndexScan scan;
   scan.OpenScan(indexHandle, ...)
   while ((rc = scan.GetNextEntry(rid)) != IX_EOF) {
      <i>error checking</i>;
      <i>delete record</i>;
      // attrValue is value of indexed attribute
      indexHandle.DeleteEntry(attrValue, rid); }
</pre>

Depending on your design, which simplifications you make, and how you
manage deletions, making sure this code will work may require a
varying amount of effort.  However, it will enable your query
processor (Part 4) to efficiently perform <tt>delete</tt> operations
based on indexed attributes.

<p> You may assume that during a retrieval scan (for selection, join,
and update operations) no index entries will be inserted or deleted.
You also may assume that during a deletion scan, no other index
records will be inserted or deleted, and no retrieval scans will be
underway.  In the basic RedBase system, IX clients will ensure that
these types of conflicting operations/scans can never occur.

<li> Depending on your design, it may require some extra effort for
scans to always return RIDs such that the corresponding attribute
values are in increasing (actually nondecreasing) order. This property
is <i>not</i> required in the project, however you may find it useful
later on, e.g., if you decide to use index scans to produce a sorted
relation. Note that one of the provided tests does exploit this
property, but passing this test is not required.

</ul>

<a name="misc">
<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>Miscellaneous</b></center>
</font></td></tr>
</table>

<ul>

<li> As with the RM component, for the IX component you may find it
convenient to use an internal header file (<tt>ix_internal.h</tt>,
say), along with the external header file <tt>ix.h</tt> and the global
header file <tt>redbase.h</tt>.

<p><li> Return codes and error handling should continue in the style
you adopted for the RM component.

<p><li> You are again expected to include comments in your code, and
to submit a 1-2 page description (in a plain text file
<tt>ix_DOC</tt>) covering your design, key data structures, testing
strategy, and known bugs, and citing any assistance you received in
design or debugging.  Since the specification and implementation
suggestions are somewhat looser for this component than they were for
Part 1, please be sure to explain any high-level algorithmic decisions
you needed to make.

<p><li> As in the RM component, after you submit your project part you
will receive an email message from the TA asking you to describe
your design decisions and implementation strategy for specific parts
of the IX component.  You will be expected to respond within 48 hours
with a short message and pointers to the relevant code.

<p><li> Running the <tt>setup</tt> script for this component copies an
<tt>ix_test.cc</tt> program, but as always the tests are not
comprehensive and you will need to create more tests in order to
thoroughly exercise your code.  We will use the same testing shell
with our (surprise) tests in order to check your component for
correctness.  IX component tests from students in previous years are
in the test repository <tt>/usr/class/cs346/redbase/testers/</tt>.
Note that some of these tests were designed for hash indexes, which
only support the equality comparison operator, so the interface for
<tt>IX_IndexScan::OpenScan</tt> is somewhat different and those tests
would need to be modified for this year's project.

<p><li> If you are aiming to win the RedBase Efficiency Contest then it
is again very important to consider (and measure) I/O efficiency as
you develop your code.

<p><li> Part 2 should be submitted electronically in the same way you
submitted Part 1.  Please compile using the <tt>-DPF_STATS</tt> flag,
remember to run the "<tt>submit -c</tt>" script with argument
"<tt>2</tt>" (for project part 2), and be sure to check the file
<tt>submit.ix</tt> before issuing the final "<tt>submit -s 2</tt>"
command. Similar to Part 1, the TA test program will link with
<code>libix.a</code> which should be the result of running
"<code>make</code>" from within your submission directory, and
everything must link correctly if the test program calls methods in
<code>ix.h</code>.

</ul>

</BODY>
